import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * 大根堆
 */
@SuppressWarnings({"all"})
public class BigHeap {

    private int[] elements; // 存储堆的元素

    private int useSize; // 堆的大小

    private final int DEFAULT_CAPACITY = 10; // 默认容量

    public BigHeap(){
        this.elements = new int[DEFAULT_CAPACITY]; // 默认初始堆的大小为10
        this.useSize = 0;
    }

    // 根据给定的数组向下调整构建大根堆 时间复杂度O(n)
    public void creadHeap(int[] data){
        // 依次向下调整初始数组的每一个元素 构建成堆
        // 从后往前找父节点
        this.elements = data;
        this.useSize = data.length;
        for (int parent = (useSize-1-1) / 2; parent >= 0; parent--) {
            siftDown(parent, useSize);
        }
    }

    // 向下调整
    // parent为要调整的父节点 len为每颗子树的调整范围
    private void siftDown(int parent, int len){
        int child = 2 * parent + 1; // 找到左孩子
        while (child < len){
            if (child + 1 < len && elements[child+1] > elements[child]){
                child = child + 1; // 保证child指向的位置一定是子节点中最大的 再与parent进行比较
            }
            if (elements[child] > elements[parent]){
                swap(elements, child, parent);
                parent = child; // 继续向下调整
                child = 2 * parent + 1;
            }else {
                break;
            }
        }
    }

    // 判断堆是否为满
    public boolean isFull(){
        return useSize == elements.length;
    }

    // 入堆
    public void offer(int val){
        if (isFull()){
            elements = Arrays.copyOf(elements, elements.length + DEFAULT_CAPACITY); // 扩容
        }
        elements[useSize++] = val;
        // 向上调整
        siftUp(useSize-1);
    }

    // 向上调整 用于插入元素 每次插入元素放入数组最后的位置（注意容量） 然后向上调整重新构造
    private void siftUp(int child){
        // 依次与parent比较 若比parent大 则交换
        int parent = (child - 1) / 2;
        while (parent >= 0){
            if (elements[parent] < elements[child]){
                swap(elements, parent, child);
                child = parent;
                parent = (child - 1) / 2;
            }else {
                break;
            }
        }
    }

    // 判断是否为空
    public boolean isEmpty(){
        return useSize == 0;
    }

    // 删除堆顶元素 让堆顶元素和最后一个值替换 useSize-- 并且重新向下调整以堆顶元素起始的堆
    public int pop(){
        if (isEmpty()){
            throw new RuntimeException("堆为空");
        }
        int ret = elements[0];
        swap(elements, 0, useSize-1);
        useSize--;
        // 向下调整
        siftDown(0, useSize);
        return ret;
    }

    // 交换arr的i j位置值
    private void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    // 求前k个最大的值 则构造有k个元素的最小堆 每次入堆的时候和堆顶进行比较 若更大 则替换 最终剩下的就是前k个最大的值
    public int[] maxK(int[] arr, int k) {
        int[] ret = new int[k];
        // 合法性检验
        if(arr == null || k == 0) {
            return ret;
        }
        if(arr.length >= k){
            ret = Arrays.copyOf(arr, k);
            return ret;
        }
        Queue<Integer> minHeap = new PriorityQueue<>(k);
        //1、遍历数组的前K个 放到堆当中
        for(int i = 0; i < k; i++){
            minHeap.offer(arr[i]);
        }
        //2、遍历剩下的K-1个，每次和堆顶元素进行比较
        for (int i = k; i < arr.length; i++) {
            if (arr[i] > minHeap.peek()) {
                minHeap.poll(); // 出堆顶后添加
                minHeap.offer(arr[i]);
            }
        }
        //3、存储结果
        for (int i = 0; i < k; i++) {
            ret[i] = minHeap.poll();
        }
        return ret;
    }

    // 求前k个最小的值 构造大顶堆 如果新值比堆顶还要小 则替换 重新构造堆
    public int[] smallestK(int[] arr, int k) {
        int[] ret = new int[k];
        // 合法性检验
        if (arr == null || k <= 0){
            return ret;
        }
        if (k >= arr.length){
            ret = Arrays.copyOf(arr, k);
        }
        // 构造大顶堆
        Queue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        // 先将前k个值入堆
        for (int i = 0; i < k; i++) {
            maxHeap.offer(arr[i]);
        }
        // 后判断剩余n-k个元素 如果比堆顶还要小 则替换
        for (int i = k; i < arr.length; i++) {
            if (arr[i] < maxHeap.peek()){
                maxHeap.poll();
                maxHeap.offer(arr[i]);
            }
        }
        // 存储并返回结果
        for (int i = 0; i < k; i++) {
            ret[i] = maxHeap.poll();
        }
        return ret;
    }

    // 以数组方式输出堆
    public void showHeap(){
        for (int i = 0; i < useSize; i++) {
            System.out.print(elements[i] + " ");
        }
        System.out.println();
    }

    // 堆排序 升序 使用大根堆 每次选取堆顶和未排序的最后一个元素进行交换 然后调整0下标为父节点的堆
    // 时间复杂度 O(nlogn) 空间复杂度 O(1)
    public void heapSort(){
        int end = useSize - 1;
        while (end > 0){
            swap(elements, 0, end);
            siftDown(0, end);
            end--;
        }
    }
}
